Validating Statements and Introduction to Proofs
Validating Statements: Concept and Need for Proofs
In mathematics, statements are not accepted as true simply because they seem plausible, hold for many examples, or are believed by many people. Mathematical truth requires rigorous verification. Validating a statement in mathematics and logic means definitively establishing its truth value (either True or False) based on the fundamental building blocks of mathematics: definitions, axioms (postulates), and previously proven theorems.
This rigorous process distinguishes mathematical truth from empirical observations or inductive reasoning. While observing patterns or testing examples can be helpful for formulating conjectures (educated guesses), they are not sufficient to *prove* a statement is universally true, especially when the statement refers to an infinite set of cases (like "for all natural numbers", "for all real numbers", etc.).
Consider the statement: "$n^2 + n + 41$ is a prime number for all natural numbers $n$."
- For $n=1$, $1^2+1+41 = 43$ (Prime)
- For $n=2$, $2^2+2+41 = 4+2+41 = 47$ (Prime)
- For $n=3$, $3^2+3+41 = 9+3+41 = 53$ (Prime)
- ... (This pattern continues for many values)
- For $n=39$, $39^2+39+41 = 1521+39+41 = 1601$ (Prime)
- For $n=40$, $40^2+40+41 = 1600+40+41 = 1681$. Is 1681 prime? $\sqrt{1681} = 41$. So, $1681 = 41 \times 41$. 1681 is not prime.
This shows that even after verifying for 39 consecutive natural numbers, the statement turns out to be false for $n=40$. This highlights why checking examples, however numerous, is not a substitute for a proof when validating a statement about an infinite set.
The Indispensable Role of Proofs
A mathematical proof is a step-by-step logical argument that uses deductive reasoning to demonstrate the truth of a statement. Each step in a proof must follow logically from the previous steps, from definitions, axioms, or established theorems. Proofs lead to absolute certainty within the chosen mathematical system.
Proofs are essential in mathematics for several fundamental reasons:
- Establishing Certainty and Rigor: Proofs provide an undeniable, universally accepted verification of a statement's truth. They eliminate doubt and subjectivity, ensuring that mathematical results are robust and reliable.
- Ensuring Generality: A well-constructed proof for a statement like "For all even integers $n$, $n^2$ is even" validates the statement for the *entire* infinite set of even integers, not just the ones we can test.
- Developing Deep Understanding: The process of creating or dissecting a proof often clarifies the relationships between different mathematical concepts and provides insight into *why* a statement is true, not just that it *is* true.
- Building a Cumulative Body of Knowledge: Once a statement is proven, it becomes a theorem. Theorems serve as verified building blocks that can be confidently used in the proofs of other, more advanced statements. This allows mathematics to build upon a secure foundation.
- Communication: Proofs are the primary means by which mathematicians communicate and justify their results to others in the field.
In summary, validating mathematical statements, especially those asserting properties "for all" elements in a set, requires more than just checking examples. It demands the construction of a logical proof.
Competitive Exam Pointer: Proofs Introduction
While competitive exams might not always require you to construct complex formal proofs from scratch, understanding the concept and the necessity of proofs is important. You should know:
- Why examples are insufficient for proving universal statements (the need for counterexamples).
- That a proof is a sequence of logical deductions.
- That proofs are based on definitions, axioms, and previously proven theorems.
- That proofs establish truth with certainty for the entire domain.
Basic proof techniques (like direct proof, contrapositive, contradiction) are often tested conceptually or by asking you to apply them to simple cases.
Methods of Validating Statements (Direct Proof - Implicit)
When tasked with validating a mathematical statement, particularly one in the form of a conditional statement ($p \implies q$, "If $p$, then $q$"), one of the most fundamental and intuitive approaches is the direct proof method. This method proceeds by directly demonstrating that the truth of the hypothesis logically leads to the truth of the conclusion.
Concept of Direct Proof for $p \implies q$
The structure of a direct proof for a conditional statement $p \implies q$ follows a straightforward logical path. The goal is to show that there is no scenario where $p$ is true and $q$ is false, by starting with the assumption that $p$ is true and deducing $q$.
The steps involved are:
- Assume the Hypothesis is True: Begin the proof by assuming that the statement $p$ (the hypothesis) is true. This is a temporary assumption made solely for the purpose of exploring its logical consequences.
- Utilise Definitions, Axioms, and Known Theorems: Draw upon the definitions of the terms involved in the statement, the fundamental axioms (basic truths assumed without proof) of the mathematical system, and any relevant theorems that have already been rigorously proven.
- Construct a Chain of Logical Deductions: From the initial assumption that $p$ is true, derive a sequence of new statements. Each new statement in the sequence must logically follow from the previous statements, combined with definitions, axioms, or proven theorems. This is the core of the deductive reasoning process. Ensure each step is justified and clear.
- Arrive at the Conclusion: Continue the chain of logical deductions until you reach the statement $q$ (the conclusion). If you can show that the truth of $p$ necessarily forces $q$ to be true through valid logical steps, you have completed the direct proof.
If you successfully complete these steps, you have rigorously demonstrated that the conditional statement $p \implies q$ is true. You have shown that whenever $p$ holds, $q$ must logically follow.
Example 1. Validate the statement: "If $n$ is an even integer, then $n^2$ is an even integer." (Use a direct proof).
Answer:
We want to prove the statement $p \implies q$, where:
- $p$: $n$ is an even integer.
- $q$: $n^2$ is an even integer.
Proof:
1. Assume the hypothesis $p$ is true: Assume $n$ is an even integer.
2. Use Definition: By the definition of an even integer, if $n$ is even, then $n$ can be expressed as $n = 2k$ for some integer $k$.
$n = 2k$
(Definition of even integer)
3. Consider the conclusion: We need to show that $n^2$ is even. Let's work with $n^2$ using our assumption about $n$:
$n^2 = (2k)^2$
(Substituting $n=2k$)
$n^2 = 4k^2$
(Algebra)
4. Deduce towards the definition of even: To show $n^2$ is even, we need to express it in the form $2 \times (\text{some integer})$. We can rewrite $4k^2$ as $2 \times (2k^2)$.
$n^2 = 2(2k^2)$
(Factoring)
5. Arrive at the conclusion $q$: Since $k$ is an integer, $k^2$ is also an integer. Therefore, $2k^2$ is also an integer. Let $m = 2k^2$. Then we have $n^2 = 2m$, where $m$ is an integer. By the definition of an even integer, this means $n^2$ is an even integer.
We started by assuming $n$ is an even integer ($p$) and through a series of logical steps based on definitions and algebra, we concluded that $n^2$ is an even integer ($q$).
Thus, the statement "If $n$ is an even integer, then $n^2$ is an even integer" is validated (proven True) by this direct proof.
Example 2. Validate the statement: "If $x$ and $y$ are odd integers, then $x+y$ is an even integer." (Use a direct proof).
Answer:
We want to prove $p \implies q$, where:
- $p$: $x$ and $y$ are odd integers.
- $q$: $x+y$ is an even integer.
Proof:
1. Assume the hypothesis $p$ is true: Assume $x$ and $y$ are odd integers.
2. Use Definition: By the definition of an odd integer, if $x$ is odd, then $x$ can be written as $x = 2k + 1$ for some integer $k$. Similarly, if $y$ is odd, then $y$ can be written as $y = 2m + 1$ for some integer $m$. (We use different variables $k$ and $m$ because $x$ and $y$ might be different odd numbers).
$x = 2k + 1$ for some integer $k$
(Definition of odd integer)
$y = 2m + 1$ for some integer $m$
(Definition of odd integer)
3. Consider the conclusion: We need to show that $x+y$ is even. Let's find the sum $x+y$ using our expressions for $x$ and $y$:
$x + y = (2k + 1) + (2m + 1)$
(Substituting $x$ and $y$)
$x + y = 2k + 1 + 2m + 1$
(Removing parentheses)
$x + y = 2k + 2m + 2$
(Combining constants)
4. Deduce towards the definition of even: To show $x+y$ is even, we need to express it in the form $2 \times (\text{some integer})$. We can factor out 2 from the expression $2k + 2m + 2$:
$x + y = 2(k + m + 1)$
(Factoring)
5. Arrive at the conclusion $q$: Since $k$ and $m$ are integers, their sum $k+m$ is an integer, and $k+m+1$ is also an integer. Let $N = k+m+1$. Then we have $x+y = 2N$, where $N$ is an integer. By the definition of an even integer, this means $x+y$ is an even integer.
We started by assuming $x$ and $y$ are odd integers ($p$) and through a series of logical steps based on definitions and algebra, we concluded that $x+y$ is an even integer ($q$).
Thus, the statement "If $x$ and $y$ are odd integers, then $x+y$ is an even integer" is validated (proven True) by this direct proof.
Direct proof is the most intuitive method for proving conditional statements when it is feasible to directly follow from the hypothesis to the conclusion. However, for some statements, the path from $\sim q$ to $\sim p$ (using the contrapositive) or assuming the negation of the entire statement (proof by contradiction) might be more accessible.
Competitive Exam Pointer: Direct Proof
Direct proof is a fundamental technique. For exams, you should understand the structure:
- To prove $p \implies q$ directly, you assume $p$ is true and use logic, definitions, and theorems to deduce $q$ is true.
- Each step in the deduction must be logically sound.
- Practice applying direct proof to simple statements involving properties of numbers (even/odd, divisibility, etc.) or basic algebra.
- Be clear about the definitions you are using (e.g., definition of even, odd, divisible).
Direct proofs are often the first proof method taught and are applicable to many types of mathematical statements.
Proof by Contrapositive (Implicit)
Sometimes, attempting a direct proof of a conditional statement $p \implies q$ can be difficult or lead to dead ends. The hypothesis $p$ might not provide enough structure to directly deduce $q$. In such cases, an alternative proof technique that leverages logical equivalence can be very effective: Proof by Contrapositive.
Concept of Proof by Contrapositive for $p \implies q$
This method is based on the fundamental logical equivalence between a conditional statement and its contrapositive. As we established earlier ($p \implies q \equiv \sim q \implies \sim p$), these two statements always have the same truth value. If one is true, the other is true; if one is false, the other is false.
Therefore, to prove that the original statement $p \implies q$ is true, we can equivalently prove that its contrapositive $\sim q \implies \sim p$ is true. The advantage is that the contrapositive might be easier to prove directly than the original statement.
The strategy for a proof by contrapositive for $p \implies q$ is:
- Formulate the Contrapositive: Clearly state the contrapositive of the original statement. This is the statement "If not $q$, then not $p$" ($\sim q \implies \sim p$).
- Assume the Hypothesis of the Contrapositive is True: Begin the proof by assuming that the statement $\sim q$ (the negation of the original conclusion) is true.
- Utilise Definitions, Axioms, and Known Theorems: As in a direct proof, draw upon established mathematical knowledge relevant to $\sim q$ and the variables involved.
- Construct a Chain of Logical Deductions: From the assumption that $\sim q$ is true, derive a sequence of new statements using valid logical steps.
- Arrive at the Conclusion of the Contrapositive: Continue the deductions until you reach the statement $\sim p$ (the negation of the original hypothesis).
If you successfully construct a direct proof for $\sim q \implies \sim p$, then by the logical equivalence, you have also proven the original statement $p \implies q$ to be true.
Example 1. Validate the statement: "If $n^2$ is an even integer, then $n$ is an even integer." (Use proof by contrapositive).
Answer:
We want to prove the statement $p \implies q$, where:
- $p$: $n^2$ is an even integer.
- $q$: $n$ is an even integer.
A direct proof starting with $n^2 = 2k$ would require reasoning about $\sqrt{2k}$, which can be cumbersome. Let's use proof by contrapositive.
Proof by Contrapositive:
1. Formulate the Contrapositive ($\sim q \implies \sim p$):
- $\sim q$: $n$ is not an even integer. In the domain of integers, "not even" is equivalent to "odd". So, $\sim q$ is "$n$ is an odd integer".
- $\sim p$: $n^2$ is not an even integer. This is equivalent to "$n^2$ is an odd integer".
The contrapositive statement is: "If $n$ is an odd integer, then $n^2$ is an odd integer."
2. Assume the hypothesis of the contrapositive ($\sim q$) is true: Assume $n$ is an odd integer.
3. Use Definition: By the definition of an odd integer, if $n$ is odd, then $n$ can be written in the form $n = 2k + 1$ for some integer $k$.
$n = 2k + 1$ for some integer $k$
(Definition of odd integer)
4. Deduce towards the conclusion of the contrapositive ($\sim p$): We need to show that $n^2$ is odd. Let's find $n^2$ using our expression for $n$:
$n^2 = (2k + 1)^2$
(Substituting $n=2k+1$)
$n^2 = (2k)^2 + 2(2k)(1) + 1^2$
(Expanding the square)
$n^2 = 4k^2 + 4k + 1$
(Simplifying)
5. Show it fits the definition of odd: To show $n^2$ is odd, we need to express it in the form $2 \times (\text{some integer}) + 1$. We can factor out 2 from the first two terms:
$n^2 = 2(2k^2 + 2k) + 1$
(Factoring)
6. Arrive at the conclusion $\sim p$: Since $k$ is an integer, $k^2$ is an integer, and $2k$ is an integer. The sum of integers $2k^2 + 2k$ is also an integer. Let $m = 2k^2 + 2k$. Then we have $n^2 = 2m + 1$, where $m$ is an integer. By the definition of an odd integer, this means $n^2$ is an odd integer.
We have successfully proven the contrapositive statement "If $n$ is an odd integer, then $n^2$ is an odd integer" ($\sim q \implies \sim p$) using a direct proof method.
Since the contrapositive statement $\sim q \implies \sim p$ is logically equivalent to the original statement $p \implies q$, we conclude that the original statement "If $n^2$ is an even integer, then $n$ is an even integer" is validated (proven true).
Example 2. Validate the statement: "If $3n+2$ is odd, then $n$ is odd." (Use proof by contrapositive, assuming $n$ is an integer).
Answer:
We want to prove $p \implies q$, where:
- $p$: $3n+2$ is odd.
- $q$: $n$ is odd.
A direct proof starting with $3n+2 = 2k+1$ would involve manipulating the expression for $n$: $3n = 2k - 1$. Expressing $n$ in terms of $k$ requires division by 3, which might not result in an integer $k$. It's trickier. Let's use proof by contrapositive.
Proof by Contrapositive:
1. Formulate the Contrapositive ($\sim q \implies \sim p$):
- $\sim q$: $n$ is not odd. In the domain of integers, this means $n$ is even. So, $\sim q$ is "$n$ is an even integer".
- $\sim p$: $3n+2$ is not odd. This means $3n+2$ is even. So, $\sim p$ is "$3n+2$ is an even integer".
The contrapositive statement is: "If $n$ is an even integer, then $3n+2$ is an even integer."
2. Assume the hypothesis of the contrapositive ($\sim q$) is true: Assume $n$ is an even integer.
3. Use Definition: By the definition of an even integer, if $n$ is even, then $n$ can be written in the form $n = 2k$ for some integer $k$.
$n = 2k$ for some integer $k$
(Definition of even integer)
4. Deduce towards the conclusion of the contrapositive ($\sim p$): We need to show that $3n+2$ is even. Let's substitute the expression for $n$ into $3n+2$:
$3n + 2 = 3(2k) + 2$
(Substituting $n=2k$)
$3n + 2 = 6k + 2$
(Simplifying)
5. Show it fits the definition of even: To show $6k+2$ is even, we need to express it in the form $2 \times (\text{some integer})$. We can factor out 2:
$3n + 2 = 2(3k + 1)$
(Factoring)
6. Arrive at the conclusion $\sim p$: Since $k$ is an integer, $3k$ is an integer, and $3k+1$ is also an integer. Let $m = 3k+1$. Then we have $3n+2 = 2m$, where $m$ is an integer. By the definition of an even integer, this means $3n+2$ is an even integer.
We have successfully proven the contrapositive statement "If $n$ is an even integer, then $3n+2$ is an even integer" ($\sim q \implies \sim p$) using a direct proof method.
Since the contrapositive statement $\sim q \implies \sim p$ is logically equivalent to the original statement $p \implies q$, we conclude that the original statement "If $3n+2$ is odd, then $n$ is odd" is validated (proven true).
Proof by contrapositive is a very powerful technique when it's easier to reason about the negation of the conclusion leading to the negation of the hypothesis than to directly reason from the hypothesis to the conclusion.
Competitive Exam Pointer: Proof by Contrapositive
Proof by contrapositive is a frequent method in logic and proof-based questions.
- Method: To prove $p \implies q$, you instead prove its contrapositive $\sim q \implies \sim p$.
- The proof of the contrapositive is done using a direct proof: Assume $\sim q$ is true, and logically deduce $\sim p$ is true.
- This method is useful when negating the conclusion ($\sim q$) provides a more convenient starting point or structure than the original hypothesis ($p$).
- Remember the logical equivalence: $p \implies q \equiv \sim q \implies \sim p$.
- Practice identifying $\sim p$ and $\sim q$ correctly, especially when $p$ or $q$ are compound statements or involve inequalities.
Being comfortable with proof by contrapositive expands your toolkit for validating mathematical statements.
Proof by Contradiction (Implicit)
While direct proof and proof by contrapositive are powerful techniques for validating conditional statements, sometimes neither approach is straightforward. In such situations, another indirect proof method, known as **proof by contradiction** (or *reductio ad absurdum*, meaning "reduction to absurdity"), can be used.
Concept of Proof by Contradiction
The core idea behind proof by contradiction is to show that if the statement you want to prove true were actually false, it would lead to a logical impossibility or a contradiction. Since a logical system cannot contain contradictions, the initial assumption (that the statement is false) must be incorrect. Therefore, the original statement must be true.
The steps to prove a statement $p$ is true using proof by contradiction are:
- Assume the Negation is True: Begin the proof by assuming that the statement you want to prove, $p$, is false. This is equivalent to assuming its negation, $\sim p$, is true. This is your temporary assumption for the sake of contradiction.
- Use the Assumption and Known Information: Use this assumption ($\sim p$) along with definitions, axioms, previously proven theorems, and any given information or premises.
- Derive a Contradiction: Through a chain of valid logical deductions from your assumption and known facts, arrive at a conclusion that is logically impossible. A contradiction is a statement that is always false, such as:
- A statement that directly conflicts with a known definition, axiom, or theorem (e.g., deducing that $1=0$ in arithmetic).
- A statement that contradicts your initial assumption ($\sim p$).
- A statement of the form $q \land (\sim q)$, which asserts that something is both true and false simultaneously (e.g., "The number is even and the number is not even").
- Conclude that the Assumption is False: Since assuming $\sim p$ logically led to a contradiction, the assumption $\sim p$ cannot be true.
- Conclude that the Original Statement is True: If the negation $\sim p$ is false, then by the law of excluded middle, the original statement $p$ must be true.
Proof by contradiction can be used to prove any type of statement, including conditional statements ($p \implies q$). To prove $p \implies q$ by contradiction, you assume its negation is true. The negation of $p \implies q$ is logically equivalent to $p \land \sim q$. So, the assumption you make at the beginning of the proof is "assume $p$ is true AND $q$ is false", and then you deduce a contradiction.
Example 1. Validate the statement: "$\sqrt{2}$ is an irrational number." (Use proof by contradiction).
Answer:
Let $p$: $\sqrt{2}$ is an irrational number.
We want to prove that $p$ is true using proof by contradiction.
Proof by Contradiction:
1. Assume the negation $\sim p$ is true: Assume that $\sqrt{2}$ is not an irrational number. By the definition of irrational numbers, this means we assume $\sqrt{2}$ is a rational number.
2. Use the assumption and definitions: By the definition of a rational number, if $\sqrt{2}$ is rational, then it can be written as a fraction $\frac{a}{b}$, where $a$ and $b$ are integers, $b \neq 0$, and the fraction $\frac{a}{b}$ is in its **lowest terms** (meaning $a$ and $b$ have no common positive integer factors other than 1. This is a crucial part of the definition for setting up the contradiction later).
Assume $\sqrt{2} = \frac{a}{b}$
(where $a, b \in \mathbb{Z}, b \neq 0$, and $\text{gcd}(a, b) = 1$)
3. Deduce consequences:
- Square both sides of the equation:
$(\sqrt{2})^2 = \left(\frac{a}{b}\right)^2$
$2 = \frac{a^2}{b^2}$
- Multiply both sides by $b^2$:
$2b^2 = a^2$
...(i)
- Equation (i) shows that $a^2$ is equal to 2 times an integer ($b^2$). By the definition of an even number, this means $a^2$ must be an even integer.
- Now, we use a previously known result (proven, for instance, by contrapositive as in the previous section): "If $n^2$ is an even integer, then $n$ is an even integer". Applying this to $a$, we conclude that $a$ must also be an even integer.
- Since $a$ is even, by the definition of an even integer, $a$ can be written as $a = 2k$ for some integer $k$.
- Substitute this expression for $a$ back into equation (i):
$2b^2 = (2k)^2$
$2b^2 = 4k^2$
- Divide both sides by 2:
$b^2 = 2k^2$
This equation shows that $b^2$ is equal to 2 times an integer ($k^2$). By the definition of an even number, this means $b^2$ must be an even integer.
- Again, applying the result "If $n^2$ is an even integer, then $n$ is an even integer" to $b$, we conclude that $b$ must also be an even integer.
$a = 2k$
(Definition of even integer)
4. Derive a Contradiction: From our deductions, we found that both $a$ is an even integer and $b$ is an even integer. By the definition of even numbers, this means both $a$ and $b$ are divisible by 2. Thus, $a$ and $b$ share a common factor of 2. However, this directly contradicts our initial assumption (part of the definition of a rational number in lowest terms) that the fraction $\frac{a}{b}$ was in its **lowest terms**, meaning $a$ and $b$ have no common factors other than 1.
This is a statement of the form $R \land (\sim R)$, where $R$ is "$\frac{a}{b}$ is in lowest terms" and $\sim R$ is "$\frac{a}{b}$ has a common factor of 2".
5. Conclude the assumption is false: Since the assumption that $\sqrt{2}$ is rational led through valid logic to a contradiction, this assumption must be false.
6. Conclude the original statement is true: If the assumption "$\sqrt{2}$ is rational" ($\sim p$) is false, then its negation "$\sqrt{2}$ is not rational" (which is our original statement $p$, "$\sqrt{2}$ is irrational") must be true.
Thus, the statement "$\sqrt{2}$ is an irrational number" is validated (proven True) by proof by contradiction.
Example 2. Validate the statement: "If $x$ is a rational number and $y$ is an irrational number, then $x+y$ is an irrational number." (Use proof by contradiction).
Answer:
We want to prove the statement $p \implies q$, where:
- $p$: $x$ is a rational number and $y$ is an irrational number. ($x \in \mathbb{Q} \land y \notin \mathbb{Q}$)
- $q$: $x+y$ is an irrational number. ($x+y \notin \mathbb{Q}$)
We will use proof by contradiction for the conditional statement $p \implies q$. This involves assuming the negation of the entire statement $p \implies q$. The negation is $\sim (p \implies q) \equiv \sim (\sim p \lor q) \equiv p \land \sim q$.
Proof by Contradiction:
1. Assume the negation of the statement is true: Assume that "If $x$ is rational and $y$ is irrational, then $x+y$ is irrational" is false. This is equivalent to assuming that the hypothesis is true AND the conclusion is false.
Assume $x$ is rational and $y$ is irrational, AND $x+y$ is rational.
(Assumption for contradiction: $p \land \sim q$)
2. Use the assumptions and definitions:
- From the assumption, $x$ is rational. By definition, $x$ can be written as $x = \frac{a}{b}$ for some integers $a, b$ with $b \neq 0$.
- From the assumption, $x+y$ is rational. By definition, $x+y$ can be written as $x+y = \frac{c}{d}$ for some integers $c, d$ with $d \neq 0$.
- From the assumption, $y$ is irrational. ($y \notin \mathbb{Q}$)
$x = \frac{a}{b}$ ($a, b \in \mathbb{Z}, b \neq 0$)
(Definition of rational)
$x + y = \frac{c}{d}$ ($c, d \in \mathbb{Z}, d \neq 0$)
(Definition of rational)
3. Deduce consequences: We have expressions for $x$ and $x+y$. Let's try to express $y$ using these. From $x+y = \frac{c}{d}$, we can write $y = \frac{c}{d} - x$. Substitute the expression for $x$:
$y = \frac{c}{d} - \frac{a}{b}$
(Substitution)
To subtract fractions, find a common denominator (e.g., $bd$, assuming $b \neq 0, d \neq 0$, which is true by definition of rational numbers):
$y = \frac{cb}{db} - \frac{ad}{bd}$
$y = \frac{cb - ad}{bd}$
...(ii)
4. Derive a Contradiction: In equation (ii), $a, b, c, d$ are all integers. The product $cb$ is an integer, the product $ad$ is an integer, and their difference $cb - ad$ is an integer. The product $bd$ is an integer. Since $b \neq 0$ and $d \neq 0$, their product $bd \neq 0$.
By the definition of a rational number, the expression $\frac{cb - ad}{bd}$ represents a rational number (an integer divided by a non-zero integer).
So, equation (ii) implies that $y$ can be expressed as a rational number. This means $y$ is rational ($y \in \mathbb{Q}$).
However, one of our initial assumptions (part of $p$) was that $y$ is irrational ($y \notin \mathbb{Q}$).
We have deduced that $y$ is rational AND $y$ is irrational. This is a statement of the form $S \land (\sim S)$, which is a contradiction.
5. Conclude the assumption is false: Since assuming "($x$ is rational and $y$ is irrational) AND ($x+y$ is rational)" led to a contradiction, this assumption must be false.
6. Conclude the original statement is true: The assumption was the negation of the original statement ($p \implies q$). Since the negation is false, the original statement $p \implies q$ must be true.
Thus, the statement "If $x$ is a rational number and $y$ is an irrational number, then $x+y$ is an irrational number" is validated (proven True) by proof by contradiction.
Proof by contradiction is particularly useful when proving statements about existence ("There is no largest prime number"), statements about irrationality, or when the direct or contrapositive approach seems difficult. It works by showing the impossibility of the opposite scenario.
Competitive Exam Pointer: Proof by Contradiction
Proof by Contradiction is a very common and important proof technique tested in exams.
- Method: To prove a statement $p$, you assume its negation $\sim p$ is true and derive a contradiction ($\bot$). Since $\sim p \implies \bot$ is a tautology, $\sim p$ must be false, so $p$ is true.
- To prove $p \implies q$ by contradiction, you assume the negation $\sim(p \implies q)$, which is equivalent to assuming $p$ is true AND $q$ is false ($p \land \sim q$), and then derive a contradiction.
- Identifying the correct initial assumption (the negation of what you want to prove) is critical.
- Be clear about the contradiction you arrive at (e.g., $a, b$ are even contradicting lowest terms, $y$ is rational contradicting $y$ is irrational).
- This method is often effective for statements involving non-existence, irrationality, or when other methods seem stuck.
Practice setting up the initial assumption and tracing its logical consequences to reach a contradiction.
Checking Validity of Arguments
Mathematical proofs are a specific type of logical argument used to validate mathematical statements. More generally, an **argument** in logic is a set of statements, one of which is claimed to follow from the others. The statements providing support are called **premises** (or hypotheses), and the statement that is claimed to follow is called the **conclusion**.
When we check the **validity** of an argument, we are examining its logical structure to see if the connection between the premises and the conclusion is logically sound.
Valid Argument
An argument is considered **valid** if and only if it is impossible for all of the premises to be true while the conclusion is false. In other words, if we assume that all the premises are true, the conclusion must necessarily be true as a logical consequence.
Let an argument have premises $P_1, P_2, \dots, P_n$ and a conclusion $C$. The argument is valid if the compound statement formed by the conjunction of the premises implying the conclusion:
$(P_1 \land P_2 \land \dots \land P_n) \implies C$
is a **tautology**. If this implication is always true, regardless of the truth values of the simple statements within $P_i$ and $C$, then the argument form is valid.
It is important to distinguish between the **validity** of an argument and the **truth** of its premises or conclusion. A valid argument guarantees that *if* the premises are true, *then* the conclusion must be true. It does not guarantee that the conclusion is actually true in the real world, unless the premises are also true. A valid argument can have false premises and a true conclusion, or false premises and a false conclusion. The only combination ruled out by a valid argument is having all true premises and a false conclusion.
Invalid Argument (Fallacy)
An argument is considered **invalid** (or a **fallacy**) if the conclusion does not necessarily follow from the premises. This means that it is possible for all the premises to be true while the conclusion is false. Such a case is called a **counterexample** to the argument form.
An argument with premises $P_1, P_2, \dots, P_n$ and conclusion $C$ is invalid if the statement $(P_1 \land P_2 \land \dots \land P_n) \implies C$ is **not** a tautology. This means the implication is either a contingency or a contradiction, containing at least one row in its truth table where the premises are all true and the conclusion is false.
Checking Validity using Truth Tables
The formal method to check the validity of an argument involves truth tables:
- Translate the premises and conclusion into symbolic logic using simple statement variables ($p, q, r, \dots$) and logical connectives.
- Identify all distinct simple statements. Determine the number of rows needed ($2^n$).
- Construct a truth table with columns for all simple statements, each premise, and the conclusion.
- Evaluate the truth values for each premise ($P_i$) and the conclusion ($C$) for every row.
- Identify the rows where all premises ($P_1 \land P_2 \land \dots \land P_n$) are simultaneously True.
- In those rows where all premises are True, check the truth value of the conclusion ($C$).
- If in *every* such row, the conclusion $C$ is also True, then the argument is **valid**. (The implication $(P_1 \land \dots \land P_n) \implies C$ is a tautology).
- If there is even *one* such row where all premises are True but the conclusion $C$ is False, then the argument is **invalid** (a fallacy). (That row represents a counterexample to the argument form, and the implication $(P_1 \land \dots \land P_n) \implies C$ is not a tautology).
Example 1. Check the validity of the following argument:
Premise 1: If it is raining ($p$), then the ground is wet ($q$). ($p \implies q$)
Premise 2: It is raining. ($p$)
Conclusion: The ground is wet. ($q$)
(This is the form Modus Ponens)
Answer:
Argument form: Premises are $P_1: p \implies q$ and $P_2: p$. Conclusion is $C: q$.
We check if $(P_1 \land P_2) \implies C$, i.e., $[(p \implies q) \land p] \implies q$ is a tautology.
1. Components: $p, q$. Rows: $2^2=4$.
2. Table construction:
| $p$ | $q$ | $p \implies q$ (Premise 1) |
$p$ (Premise 2) |
$(p \implies q) \land p$ (Premises Conjoined) |
$q$ (Conclusion) |
$[(p \implies q) \land p] \implies q$ (Premises $\implies$ Conclusion) |
|---|---|---|---|---|---|---|
| T | T | T | T | T $\land$ T = T | T | T $\implies$ T = T |
| T | F | F | T | F $\land$ T = F | F | F $\implies$ F = T |
| F | T | T | F | T $\land$ F = F | T | F $\implies$ T = T |
| F | F | T | F | T $\land$ F = F | F | F $\implies$ F = T |
3. Check rows where premises are True: Look at the column "(Premises Conjoined)". The premises $(p \implies q) \land p$ are simultaneously True only in the **first row**.
4. Check conclusion in those rows: In the first row, where the premises are True, the conclusion $q$ is also True.
Since the case (Premises True $\land$ Conclusion False) never occurs (as shown by the final column being all T's), the argument form is valid.
The statement $[(p \implies q) \land p] \implies q$ is a tautology.
Therefore, the argument is Valid. This valid form is called Modus Ponens.
Example 2. Check the validity of the following argument:
Premise 1: If a number is divisible by 4 ($p$), then it is divisible by 2 ($q$). ($p \implies q$)
Premise 2: The number is divisible by 2. ($q$)
Conclusion: The number is divisible by 4. ($p$)
(This is the form Fallacy of the Converse)
Answer:
Argument form: Premises are $P_1: p \implies q$ and $P_2: q$. Conclusion is $C: p$.
We check if $(P_1 \land P_2) \implies C$, i.e., $[(p \implies q) \land q] \implies p$ is a tautology.
1. Components: $p, q$. Rows: $2^2=4$.
2. Table construction:
| $p$ | $q$ | $p \implies q$ (Premise 1) |
$q$ (Premise 2) |
$(p \implies q) \land q$ (Premises Conjoined) |
$p$ (Conclusion) |
$[(p \implies q) \land q] \implies p$ (Premises $\implies$ Conclusion) |
|---|---|---|---|---|---|---|
| T | T | T | T | T $\land$ T = T | T | T $\implies$ T = T |
| T | F | F | F | F $\land$ F = F | T | F $\implies$ T = T |
| F | T | T | T | T $\land$ T = T | F | T $\implies$ F = F |
| F | F | T | F | T $\land$ F = F | F | F $\implies$ F = T |
3. Check rows where premises are True: Look at the column "(Premises Conjoined)". The premises $(p \implies q) \land q$ are simultaneously True in the **first row** and the **third row**.
4. Check conclusion in those rows:
- In the first row, premises are True, conclusion ($p$) is True. This case is fine.
- In the **third row**, premises are True (T $\land$ T = T), but the conclusion ($p$) is **False**. This row (F $\implies$ T is T, q is T, p is F) represents a scenario where the premises are all true, but the conclusion is false. This is a **counterexample** to the argument form.
Since there is at least one case where all premises are true and the conclusion is false (specifically, the third row), the argument form is invalid. The statement $[(p \implies q) \land q] \implies p$ is not a tautology (the final column contains an F in the third row).
Therefore, the argument is Invalid. This invalid form is called the Fallacy of the Converse.
Example of Counterexample:
Let the number be 6.
- Premise 1: "If a number is divisible by 4, then it is divisible by 2." (True statement)
- Premise 2: "6 is divisible by 2." (True statement)
- Conclusion: "6 is divisible by 4." (False statement)
Here we have True premises and a False conclusion, demonstrating the invalidity of the argument.
Understanding validity is fundamental to constructing and evaluating logical arguments and mathematical proofs. A proof must be a valid argument whose premises are known to be true.
Competitive Exam Pointer: Argument Validity
Checking argument validity is a common exam question type, often using familiar argument forms.
- Definition: An argument is valid if True Premises always lead to a True Conclusion. It's invalid if True Premises can lead to a False Conclusion.
- Verification: Construct a truth table for the statement (Premise1 $\land$ Premise2 $\land \dots$) $\implies$ Conclusion.
- If the final column is ALL T's, the argument is Valid (it's a tautology).
- If the final column has at least one F, the argument is Invalid (it's not a tautology). A row where premises are T and conclusion is F is a counterexample.
- Know Common Forms: Be able to recognise and state the validity of standard argument forms like:
- Valid: Modus Ponens ($[(p \implies q) \land p] \implies q$), Modus Tollens ($[(p \implies q) \land \sim q] \implies \sim p$), Hypothetical Syllogism ($[(p \implies q) \land (q \implies r)] \implies (p \implies r)$).
- Invalid (Fallacies): Fallacy of the Converse ($[(p \implies q) \land q] \implies p$), Fallacy of the Inverse ($[(p \implies q) \land \sim p] \implies \sim q$).
- Practice translating arguments from English into symbolic form.
Being able to identify valid argument forms helps in following and constructing correct logical deductions.